#include <iostream>

using namespace std;

bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        if (n == 1) {
            return n;
        }
        if (isBadVersion(1)) {
            return 1;
        }
        int left = 1;
        int right = n;
        while (right > left + 1) {
            bool middle = isBadVersion(((int64_t) left + right) / 2);
            if (!middle) {
                left = ((int64_t) left + right) / 2;
            } else {
                right = ((int64_t) left + right) / 2;
            }
        }
        return right;
    }
};